package com.objcat.playground.algorithm.sort.bubble;

import java.util.Arrays;

/**
 * description: Bubble <br>
 * date: 2022/3/27 5:18 下午 <br>
 * author: objcat <br>
 * version: 1.0 <br>
 */
public class Bubble {
    static void bubbleSort(int[] list) {
        for (int i = 0; i < list.length - 1; i++) {
            for (int j = 0; j < list.length - 1 - i; j++) {
                if (list[j] > list[j + 1]) {
                    int temp = list[j];
                    list[j] = list[j + 1];
                    list[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] list = {5, 3, 1, 4, 2};
        Bubble.bubbleSort(list);
        System.out.println(Arrays.toString(list));
    }
}

/**
 * 冒泡排序法是非常基础的排序算法, 方法就是比较前后两个数, 根据规则进行交换
 * <p>
 * 从小到大: 前后比较 前面的比后面大就交换 一轮下来后 最后一个数一定是最大的
 * 从大到小: 前后比较 前面的比后面的小就交换 一轮下来之后 最后一个数一定是最小的
 * <p>
 * 5 3 1 4 2 开始
 * 3 1 4 2 5 第一轮 比 4 次 0:1 1:2 2:3 3:4
 * 1 3 2 4 - 第二轮 比 3 次 0:1 1:2 2:3
 * 1 2 3 - - 第三轮 比 2 次 0:1 1:2
 * 1 2 - - - 第四轮 比 1 次 0:1
 * <p>
 * 可以看到 5 个数字 比了 4 轮 第一轮比 4 次, 第二轮比 3 次 ... 第四轮比 1 次
 * 假设数组里有 n 个元素
 * 推理得出 需要比 n - 1 轮 每轮比了 n - 1 - i 次
 */